package DataStructure;

import java.util.Stack;

/**
 * 单向链表 [data|next]--->[data|next]
 *
 * @time: 2021/3/18/018 21:03
 * @author: Zhurunhe
 */
public class LinkListTest {
    public static void main(String[] args) {
        Staff s1 = new Staff(1, "zhangsan");
        Staff s2 = new Staff(2, "wangwu");
        Staff s3 = new Staff(3, "lili");
        Staff s4 = new Staff(4, "xiaoming");
        Staff s5 = new Staff(5, "wanghua");
        Staff s6 = new Staff(6, "zz");
        Staff s7 = new Staff(7, "zw");
        LinkListArray linkListArray = new LinkListArray();
        LinkListArray linkListArray2 = new LinkListArray();

        linkListArray2.addByNo(s2);
        linkListArray.addByNo(s3);
        linkListArray2.addByNo(s4);
        linkListArray.addByNo(s1);
        linkListArray2.addByNo(s5);
        linkListArray.addByNo(s6);
        linkListArray.addByNo(s7);
//        linkListArray.addByNo(s2);
//        linkListArray.show();
//        System.out.println("+++++-------------");
//        linkListArray2.show();
//        System.out.println("+++++-------------+++++");
//        Merge(linkListArray2.getHead(), linkListArray.getHead());
//        linkListArray.show();


//        System.out.println("+++++-------------");
//        Staff s11=new Staff(3,"lili+++++");
//        linkListArray.update(s11);
//        linkListArray.show();
//
//        System.out.println("+++++-------------");
//        Staff s12=new Staff(3,"lili+++++");
//        linkListArray.delete(s12);
//        linkListArray.show();

        System.out.println("-------------");
        ToReverse(linkListArray.getHead());
        linkListArray.show();

//        System.out.println("-------------+");
//        PrintList(linkListArray.getHead());

    }


    public static int getLength(Staff staff) {
        if (staff.next == null) {
            System.out.println("链表为空");
            return 0;
        }

        Staff temp = staff.next;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    //两条单向列表合并一条
    public static void Merge(Staff s1, Staff s2) {

        if (s1 == null || s1.next == null) {
            return;
        }
        if (s2 == null || s2.next == null) {
            return;
        }

        Staff temp1 = s1.next;
        Staff temp2 = s2;
        Staff next = null;

        while (temp1 != null) {
            next = temp1.next;
            while (temp2.next != null) {
                //当发现编号一样时 就退出
                if (temp1.no == temp2.next.no) {
                    break;
                }
                //temp1的值对比第二条单向链表的每个节点元素的值。
                if (temp1.no < temp2.next.no) {
                    //当一个值小于第二条链表的某一个节点的下一个节点的值时，让它插入到该节点的后面

                    temp1.next = temp2.next;//让插入值的next域为第二条链表所找到的位置（temp1.no < temp2.next.no)的 也就是temp2.next
                    temp2.next = temp1;//而之前的被插入前的temp2节点与之前的next节点断开，就让他的指针指向temp1，这样就能连接起来
                    break;
                }
                if(temp2.next.next==null){
                    //还会有最后有一个元素需要插入但它的值都大于被插入链表节点的值 只能在最后一个位置添加该元素
                    temp2.next.next=temp1;
                }



                temp2 = temp2.next;
            }
            temp1 = next;

        }



    }

    //反向打打印单向列表
    public static void PrintList(Staff head) {
        if (head == null || head.next == null) {
            return;
        }
        Stack stack = new Stack();
        Staff temp = head.next;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }

    }

    //反转单向列表
    public static void ToReverse(Staff head) {
        if (head == null || head.next == null) {
            return;
        }
        Staff next = null;//接受下一个节点 防止指针丢失
        Staff temp = head.next;
        Staff NewS = new Staff(0, "");
        while (temp != null) {
            next = temp.next;
            temp.next = NewS.next;//让temp的下一个节点指向新节点NewS的下一个节点 1————》null 2————》1————》null  -------------
            NewS.next = temp;//让NewS的下一个节点等于temp节点 如上一行注释
            temp = next;//让temp指向下一个节点
        }
        head.next = NewS.next;//让head重新接上翻转的单向列表


        //递归法
//       if(head==null||head.next==null){
//           return head;
//       }
//       Staff temp=head;
//       Staff newStaff=ToReverse(head.next);
//       temp.next.next=head;
//       head.next=null;
//       return newStaff;
    }
}

class LinkListArray {
    Staff head = new Staff(0, "");

    public Staff getHead() {
        return head;
    }

    public void add(Staff staff) {
        Staff temp = head;//需要一个辅助变量 来帮助查询下一个结点
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = staff;
    }

    public void addByNo(Staff staff) {
        Staff temp = head;
        boolean isExist = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > staff.no) {
                break;
            } else if (temp.next.no == staff.no) {
                isExist = true;
                break;
            }
            temp = temp.next;
        }
        if (isExist) {
            System.out.println(staff.no + "员工已在列表中不能添加");
        } else {
            staff.next = temp.next;
            temp.next = staff;
        }
    }

    public void delete(Staff staff) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Staff temp = head;
        boolean isExist = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == staff.no) {
                isExist = true;
                break;
            }
            temp = temp.next;
        }
        if (isExist) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到该员工");
        }
    }

    public void update(Staff staff) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Staff temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == staff.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = staff.name;

        } else {
            System.out.println("该列表中没有该员工");
        }


    }

    public void show() {

        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Staff temp = head.next;//定义一个 查看下一个指标的节点是否存在
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

class Staff {
    int no;
    String name;
    Staff next;

    public Staff(int no, String name) {
        this.name = name;
        this.no = no;
    }

    @Override
    public String toString() {
        return "Staff{" + "no=" + no + ", name='" + name + '\'' + '}';
    }
}
